package likou;

/**
 * @description: 实现 strStr()
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle
 * 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
 * 说明：
 * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
 * @title: Str
 * @author: zp
 * @date: 2022/1/19 20:17
 */
public class StrDemo {
    public static void main(String[] args) {
        System.out.println(strStr2("hello","ll0"));
    }

    /**
     * @description: Str实现的暴力破解
     * @author: zp
     * @date: 2022/1/19 20:18
     * @param: haystack
     * @param: needle
     * @return: int
     */
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
    /**
     * @description: KMP算法的实现
     * 要清楚前缀和后缀的概念
     * 示例："ABABC"
     * 前缀：B、BA、BAB、BABC (除去第一个字符 之外所有的按顺序的组合)
     * 后缀：B，BA、BAB、BABA(除去最后一个字符 之外所有的按倒序的组合)
     * 然后在两个集合中找到公共的子串 B、BA 换算成数组就是[0,1,2,0] 其中的值就是字符串长度
     * KMP的核心公式：向右移动的位数为=失配字符所在位置（也就是第几个字符为匹配上的字符串长度） - 失配字符对应的next 值（下面公共字符串的长度）
     * @author: zp
     * @date: 2022/1/19 20:19
     * @param: haystack
     * @param: needle
     * @return: int
     */
    public static int strStr2(String haystack, String needle) {
        //获取查找的字符串 和 被查找字符串的长度
        int n = haystack.length(), m = needle.length();
        //如果长度为0 直接返回
        if (m == 0) {
            return 0;
        }
        //创建公共子串的数组 大小就等于查找字符串（needle.length()）的长度
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            //如果不相等 j也大于零 向j的前一位的数组里面寻找 直到找到相等 或者j<=d的时候
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            //如果i位置的字符串和j位置的字符串相等 j++ 类似于 "AAA" [0,1,2]
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            //把j的值保存
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            //获取公共子串的长度
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            //如果不相等 就把j的位置加一
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            //当j==m的时候 也代表公共字符串相同 也就找到了要找字符串出现的第一个位置
            if (j == m) {
                return i - m + 1;
            }
        }
        //如果没找到返回-1
        return -1;
    }

}
